/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/guess-number-higher-or-lower-ii
   @Language: C++
   @Datetime: 19-06-18 10:38
   */

// Method 1, DP, Time O(n^2), Space O(n^2), Time 103ms
class Solution {
public:
	/**
	 * @param n: An integer
	 * @return: how much money you need to have to guarantee a win
	 */
	int getMoneyAmount(int n) {
		// write your code here
		vector<vector<int> > dp(n+1,vector<int>(n+1,0));
		for(int len=1; len<=n; ++len){
			for(int i=len-1; i; --i){
				int t=INT_MAX;
				for(int j=i+1; j<len; ++j)
					t=min(t,max(dp[i][j-1],dp[j+1][len])+j);
				dp[i][len]=i+1==len?i:t;
			}
		}
		return dp[1][n];
	}
};

// Method 2, memorized search, Time O(n^2), Space O(n^2), Time 201ms
class Solution {
	int core(int start, int end, vector<vector<int> > &mem){
		if(start>=end) return 0;
		if(mem[start][end]) return mem[start][end];
		int res=INT_MAX;
		for(int k=start; k<=end; ++k)
			res=min(res,max(core(start,k-1,mem),core(k+1,end,mem))+k);
		return mem[start][end]=res;
	}
public:
	/**
	 * @param n: An integer
	 * @return: how much money you need to have to guarantee a win
	 */
	int getMoneyAmount(int n) {
		// write your code here
		vector<vector<int> > mem(n+1,vector<int>(n+1,0));
		return core(1,n,mem);
	}
};
